|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
// NOTE: This code is derived from an implementation originally in dotnet/runtime:
// https://github.com/dotnet/runtime/blob/v8.0.3/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/List.cs
//
// See the commentary in https://github.com/dotnet/roslyn/pull/50156 for notes on incorporating changes made to the
// reference implementation.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Threading;
using Microsoft.CodeAnalysis.Collections.Internal;
namespace Microsoft.CodeAnalysis.Collections
{
/// <summary>
/// Represents a strongly typed list of objects that can be accessed by index. Provides methods to search, sort, and
/// manipulate lists.
/// </summary>
/// <remarks>
/// <para>This collection has the same performance characteristics as <see cref="List{T}"/>, but uses segmented
/// arrays to avoid allocations in the Large Object Heap.</para>
/// </remarks>
/// <typeparam name="T">The type of elements in the list.</typeparam>
[DebuggerTypeProxy(typeof(ICollectionDebugView<>))]
[DebuggerDisplay("Count = {Count}")]
internal class SegmentedList<T> : IList<T>, IList, IReadOnlyList<T>
{
private const int DefaultCapacity = 4;
private const int MaxLength = 0x7FFFFFC7;
internal SegmentedArray<T> _items;
internal int _size;
internal int _version;
private static readonly SegmentedArray<T> s_emptyArray = new(0);
private static IEnumerator<T>? s_emptyEnumerator;
// Constructs a SegmentedList. The list is initially empty and has a capacity
// of zero. Upon adding the first element to the list the capacity is
// increased to DefaultCapacity, and then increased in multiples of two
// as required.
public SegmentedList()
{
_items = s_emptyArray;
}
// Constructs a SegmentedList with a given initial capacity. The list is
// initially empty, but will have room for the given number of elements
// before any reallocations are required.
//
public SegmentedList(int capacity)
{
if (capacity < 0)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
if (capacity == 0)
_items = s_emptyArray;
else
_items = new SegmentedArray<T>(capacity);
}
// Constructs a SegmentedList, copying the contents of the given collection. The
// size and capacity of the new list will both be equal to the size of the
// given collection.
//
public SegmentedList(IEnumerable<T> collection)
{
if (collection == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
if (collection is SegmentedList<T> segmentedList)
{
_items = (SegmentedArray<T>)segmentedList._items.Clone();
_size = segmentedList._size;
return;
}
if (collection is ICollection<T> c)
{
var count = c.Count;
if (count == 0)
{
_items = s_emptyArray;
return;
}
else
{
_items = new SegmentedArray<T>(count);
if (SegmentedCollectionsMarshal.AsSegments(_items) is { Length: 1 } segments)
{
c.CopyTo(segments[0], 0);
_size = count;
return;
}
}
// Continue below to add the items
}
else
{
_items = s_emptyArray;
// Continue below to add the items
}
using var en = collection.GetEnumerator();
while (en.MoveNext())
{
Add(en.Current);
}
}
// Gets and sets the capacity of this list. The capacity is the size of
// the internal array used to hold items. When set, the internal
// array of the list is reallocated to the given capacity.
//
public int Capacity
{
get => _items.Length;
set
{
if (value < _size)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
}
if (value == _items.Length)
return;
if (value <= 0)
{
_items = s_emptyArray;
return;
}
if (_items.Length == 0)
{
// No data from existing array to reuse, just create a new one.
_items = new SegmentedArray<T>(value);
}
else
{
// Rather than creating a copy of _items, instead reuse as much of it's data as possible.
_items = CreateNewSegmentedArrayReusingOldSegments(_items, value);
}
}
}
private static SegmentedArray<T> CreateNewSegmentedArrayReusingOldSegments(SegmentedArray<T> oldArray, int newSize)
{
var segments = SegmentedCollectionsMarshal.AsSegments(oldArray);
var oldSegmentCount = segments.Length;
var newSegmentCount = (newSize + SegmentedArrayHelper.GetSegmentSize<T>() - 1) >> SegmentedArrayHelper.GetSegmentShift<T>();
// Grow the array of segments, if necessary
Array.Resize(ref segments, newSegmentCount);
// Resize all segments to full segment size from the last old segment to the next to last
// new segment.
for (var i = oldSegmentCount - 1; i < newSegmentCount - 1; i++)
Array.Resize(ref segments[i], SegmentedArrayHelper.GetSegmentSize<T>());
// Resize the last segment
var lastSegmentSize = newSize - ((newSegmentCount - 1) << SegmentedArrayHelper.GetSegmentShift<T>());
Array.Resize(ref segments[newSegmentCount - 1], lastSegmentSize);
return SegmentedCollectionsMarshal.AsSegmentedArray(newSize, segments);
}
// Read-only property describing how many elements are in the SegmentedList.
public int Count => _size;
bool IList.IsFixedSize => false;
// Is this SegmentedList read-only?
bool ICollection<T>.IsReadOnly => false;
bool IList.IsReadOnly => false;
// Is this SegmentedList synchronized (thread-safe)?
bool ICollection.IsSynchronized => false;
// Synchronization root for this object.
object ICollection.SyncRoot => this;
// Sets or Gets the element at the given index.
public T this[int index]
{
get
{
// Following trick can reduce the range check by one
if ((uint)index >= (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();
}
return _items[index];
}
set
{
if ((uint)index >= (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();
}
_items[index] = value;
_version++;
}
}
private static bool IsCompatibleObject(object? value)
{
// Non-null values are fine. Only accept nulls if T is a class or Nullable<U>.
// Note that default(T) is not equal to null for value types except when T is Nullable<U>.
return (value is T) || (value == null && default(T) == null);
}
object? IList.this[int index]
{
get => this[index];
set
{
ThrowHelper.IfNullAndNullsAreIllegalThenThrow<T>(value, ExceptionArgument.value);
try
{
this[index] = (T)value!;
}
catch (InvalidCastException)
{
ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(T));
}
}
}
// Adds the given object to the end of this list. The size of the list is
// increased by one. If required, the capacity of the list is doubled
// before adding the new element.
//
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Add(T item)
{
_version++;
var array = _items;
var size = _size;
if ((uint)size < (uint)array.Length)
{
_size = size + 1;
array[size] = item;
}
else
{
AddWithResize(item);
}
}
// Non-inline from SegmentedList.Add to improve its code quality as uncommon path
[MethodImpl(MethodImplOptions.NoInlining)]
private void AddWithResize(T item)
{
Debug.Assert(_size == _items.Length);
var size = _size;
Grow(size + 1);
_size = size + 1;
_items[size] = item;
}
int IList.Add(object? item)
{
ThrowHelper.IfNullAndNullsAreIllegalThenThrow<T>(item, ExceptionArgument.item);
try
{
Add((T)item!);
}
catch (InvalidCastException)
{
ThrowHelper.ThrowWrongValueTypeArgumentException(item, typeof(T));
}
return Count - 1;
}
// Adds the elements of the given collection to the end of this list. If
// required, the capacity of the list is increased to twice the previous
// capacity or the new size, whichever is larger.
//
public void AddRange(IEnumerable<T> collection)
{
if (collection == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
}
if (collection is ICollection<T> c)
{
var count = c.Count;
if (count > 0)
{
if (_items.Length - _size < count)
{
Grow(checked(_size + count));
}
if (c is SegmentedList<T> list)
{
SegmentedArray.Copy(list._items, 0, _items, _size, list.Count);
}
else if (c is SegmentedArray<T> array)
{
SegmentedArray.Copy(array, 0, _items, _size, array.Length);
}
else
{
var targetIndex = _size;
foreach (var item in c)
_items[targetIndex++] = item;
}
_size += count;
_version++;
}
}
else
{
using var en = collection.GetEnumerator();
while (en.MoveNext())
{
Add(en.Current);
}
}
}
public ReadOnlyCollection<T> AsReadOnly()
=> new(this);
// Searches a section of the list for a given element using a binary search
// algorithm. Elements of the list are compared to the search value using
// the given IComparer interface. If comparer is null, elements of
// the list are compared to the search value using the IComparable
// interface, which in that case must be implemented by all elements of the
// list and the given search value. This method assumes that the given
// section of the list is already sorted; if this is not the case, the
// result will be incorrect.
//
// The method returns the index of the given value in the list. If the
// list does not contain the given value, the method returns a negative
// integer. The bitwise complement operator (~) can be applied to a
// negative result to produce the index of the first element (if any) that
// is larger than the given search value. This is also the index at which
// the search value should be inserted into the list in order for the list
// to remain sorted.
//
// The method uses the Array.BinarySearch method to perform the
// search.
//
public int BinarySearch(int index, int count, T item, IComparer<T>? comparer)
{
if (index < 0)
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
if (count < 0)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
if (_size - index < count)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
return SegmentedArray.BinarySearch(_items, index, count, item, comparer);
}
public int BinarySearch(T item)
=> BinarySearch(0, Count, item, null);
public int BinarySearch(T item, IComparer<T>? comparer)
=> BinarySearch(0, Count, item, comparer);
// Clears the contents of SegmentedList.
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Clear()
{
_version++;
#if NET
if (!RuntimeHelpers.IsReferenceOrContainsReferences<T>())
{
_size = 0;
return;
}
#endif
var size = _size;
_size = 0;
if (size > 0)
{
SegmentedArray.Clear(_items, 0, size); // Clear the elements so that the gc can reclaim the references.
}
}
// Contains returns true if the specified element is in the SegmentedList.
// It does a linear, O(n) search. Equality is determined by calling
// EqualityComparer<T>.Default.Equals().
//
public bool Contains(T item)
{
// PERF: IndexOf calls Array.IndexOf, which internally
// calls EqualityComparer<T>.Default.IndexOf, which
// is specialized for different types. This
// boosts performance since instead of making a
// virtual method call each iteration of the loop,
// via EqualityComparer<T>.Default.Equals, we
// only make one virtual call to EqualityComparer.IndexOf.
return _size != 0 && IndexOf(item) >= 0;
}
bool IList.Contains(object? item)
{
if (IsCompatibleObject(item))
{
return Contains((T)item!);
}
return false;
}
public SegmentedList<TOutput> ConvertAll<TOutput>(Converter<T, TOutput> converter)
{
if (converter == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.converter);
}
var list = new SegmentedList<TOutput>(_size);
for (var i = 0; i < _size; i++)
{
list._items[i] = converter(_items[i]);
}
list._size = _size;
return list;
}
// Copies this SegmentedList into array, which must be of a
// compatible array type.
public void CopyTo(T[] array)
=> CopyTo(array, 0);
// Copies this SegmentedList into array, which must be of a
// compatible array type.
void ICollection.CopyTo(Array array, int arrayIndex)
{
if ((array != null) && (array.Rank != 1))
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
}
try
{
// Array.Copy will check for NULL.
SegmentedArray.Copy(_items, 0, array!, arrayIndex, _size);
}
catch (ArrayTypeMismatchException)
{
ThrowHelper.ThrowArgumentException_Argument_IncompatibleArrayType();
}
}
// Copies a section of this list to the given array at the given index.
//
// The method uses the Array.Copy method to copy the elements.
//
public void CopyTo(int index, T[] array, int arrayIndex, int count)
{
if (_size - index < count)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
}
// Delegate rest of error checking to Array.Copy.
SegmentedArray.Copy(_items, index, array, arrayIndex, count);
}
public void CopyTo(T[] array, int arrayIndex)
{
// Delegate rest of error checking to Array.Copy.
SegmentedArray.Copy(_items, 0, array, arrayIndex, _size);
}
/// <summary>
/// Ensures that the capacity of this list is at least the specified <paramref name="capacity"/>.
/// If the current capacity of the list is less than specified <paramref name="capacity"/>,
/// the capacity is increased by continuously twice current capacity until it is at least the specified <paramref name="capacity"/>.
/// </summary>
/// <param name="capacity">The minimum capacity to ensure.</param>
/// <returns>The new capacity of this list.</returns>
public int EnsureCapacity(int capacity)
{
if (capacity < 0)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
if (_items.Length < capacity)
{
Grow(capacity);
}
return _items.Length;
}
/// <summary>
/// Increase the capacity of this list to at least the specified <paramref name="capacity"/>.
/// </summary>
/// <param name="capacity">The minimum capacity to ensure.</param>
internal void Grow(int capacity)
{
Debug.Assert(_items.Length < capacity);
var newCapacity = 0;
if (_items.Length < SegmentedArrayHelper.GetSegmentSize<T>() / 2)
{
// The array isn't near the maximum segment size. If the array is empty, the new capacity
// should be DefaultCapacity. Otherwise, the new capacity should be double the current array size.
newCapacity = _items.Length == 0 ? DefaultCapacity : _items.Length * 2;
}
else if (_items.Length < SegmentedArrayHelper.GetSegmentSize<T>())
{
// There is only a single segment that is over half full. Increase it to a full segment.
newCapacity = SegmentedArrayHelper.GetSegmentSize<T>();
}
else
{
// If the last segment is fully sized, increase the number of segments by the desired growth rate
if (0 == (_items.Length & SegmentedArrayHelper.GetOffsetMask<T>()))
{
// This value determines the growth rate of the number of segments to use.
// For a value of 3, this means the segment count will grow at a rate of
// 1 + (1 >> 3) or 12.5%
const int segmentGrowthShiftValue = 3;
var oldSegmentCount = (_items.Length + SegmentedArrayHelper.GetSegmentSize<T>() - 1) >> SegmentedArrayHelper.GetSegmentShift<T>();
var newSegmentCount = oldSegmentCount + Math.Max(1, oldSegmentCount >> segmentGrowthShiftValue);
newCapacity = SegmentedArrayHelper.GetSegmentSize<T>() * newSegmentCount;
}
}
// If the computed capacity is less than specified, set to the original argument.
// Capacities exceeding Array.MaxLength will be surfaced as OutOfMemoryException by Array.Resize.
if (newCapacity < capacity)
newCapacity = capacity;
if (newCapacity > SegmentedArrayHelper.GetSegmentSize<T>())
{
// If the last segment isn't fully sized, increase the new capacity such that it will be.
var lastSegmentLength = newCapacity & SegmentedArrayHelper.GetOffsetMask<T>();
if (lastSegmentLength > 0)
newCapacity = (newCapacity - lastSegmentLength) + SegmentedArrayHelper.GetSegmentSize<T>();
// Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
// Note that this check works even when _items.Length overflowed thanks to the (uint) cast
if ((uint)newCapacity > MaxLength)
newCapacity = MaxLength;
}
Capacity = newCapacity;
}
public bool Exists(Predicate<T> match)
=> FindIndex(match) != -1;
public T? Find(Predicate<T> match)
{
if (match == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
for (var i = 0; i < _size; i++)
{
if (match(_items[i]))
{
return _items[i];
}
}
return default;
}
public SegmentedList<T> FindAll(Predicate<T> match)
{
if (match == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
var list = new SegmentedList<T>();
for (var i = 0; i < _size; i++)
{
if (match(_items[i]))
{
list.Add(_items[i]);
}
}
return list;
}
public int FindIndex(Predicate<T> match)
=> FindIndex(0, _size, match);
public int FindIndex(int startIndex, Predicate<T> match)
=> FindIndex(startIndex, _size - startIndex, match);
public int FindIndex(int startIndex, int count, Predicate<T> match)
{
if ((uint)startIndex > (uint)_size)
{
ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_IndexMustBeLessOrEqual();
}
if (count < 0 || startIndex > _size - count)
{
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
}
if (match == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
var endIndex = startIndex + count;
for (var i = startIndex; i < endIndex; i++)
{
if (match(_items[i]))
return i;
}
return -1;
}
public T? FindLast(Predicate<T> match)
{
if (match == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
for (var i = _size - 1; i >= 0; i--)
{
if (match(_items[i]))
{
return _items[i];
}
}
return default;
}
public int FindLastIndex(Predicate<T> match)
=> FindLastIndex(_size - 1, _size, match);
public int FindLastIndex(int startIndex, Predicate<T> match)
=> FindLastIndex(startIndex, startIndex + 1, match);
public int FindLastIndex(int startIndex, int count, Predicate<T> match)
{
if (match == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
if (_size == 0)
{
// Special case for 0 length SegmentedList
if (startIndex != -1)
{
ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_IndexMustBeLess();
}
}
else
{
// Make sure we're not out of range
if ((uint)startIndex >= (uint)_size)
{
ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_IndexMustBeLess();
}
}
// 2nd have of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0.
if (count < 0 || startIndex - count + 1 < 0)
{
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
}
var endIndex = startIndex - count;
for (var i = startIndex; i > endIndex; i--)
{
if (match(_items[i]))
{
return i;
}
}
return -1;
}
public void ForEach(Action<T> action)
{
if (action == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.action);
}
var version = _version;
for (var i = 0; i < _size; i++)
{
if (version != _version)
{
break;
}
action(_items[i]);
}
if (version != _version)
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
// Returns an enumerator for this list with the given
// permission for removal of elements. If modifications made to the list
// while an enumeration is in progress, the MoveNext and
// GetObject methods of the enumerator will throw an exception.
//
public Enumerator GetEnumerator() => new(this);
IEnumerator<T> IEnumerable<T>.GetEnumerator() =>
Count == 0 ? GetEmptyEnumerator() :
GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => ((IEnumerable<T>)this).GetEnumerator();
private static IEnumerator<T> GetEmptyEnumerator()
{
return LazyInitializer.EnsureInitialized(ref s_emptyEnumerator, static () => new Enumerator(new SegmentedList<T>(0)))!;
}
public SegmentedList<T> GetRange(int index, int count)
{
if (index < 0)
{
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
if (count < 0)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
if (_size - index < count)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
}
var list = new SegmentedList<T>(count);
SegmentedArray.Copy(_items, index, list._items, 0, count);
list._size = count;
return list;
}
/// <summary>
/// Creates a shallow copy of a range of elements in the source <see cref="SegmentedList{T}" />.
/// </summary>
/// <param name="start">The zero-based <see cref="SegmentedList{T}" /> index at which the range starts.</param>
/// <param name="length">The length of the range.</param>
/// <returns>A shallow copy of a range of elements in the source <see cref="SegmentedList{T}" />.</returns>
/// <exception cref="ArgumentOutOfRangeException">
/// <paramref name="start" /> is less than 0.
/// -or-
/// <paramref name="length" /> is less than 0.
/// </exception>
/// <exception cref="ArgumentException"><paramref name="start" /> and <paramref name="length" /> do not denote a valid range of elements in the <see cref="SegmentedList{T}" />.</exception>
public SegmentedList<T> Slice(int start, int length) => GetRange(start, length);
// Returns the index of the first occurrence of a given value in a range of
// this list. The list is searched forwards from beginning to end.
// The elements of the list are compared to the given value using the
// Object.Equals method.
//
// This method uses the Array.IndexOf method to perform the
// search.
//
public int IndexOf(T item)
=> SegmentedArray.IndexOf(_items, item, 0, _size);
int IList.IndexOf(object? item)
{
if (IsCompatibleObject(item))
{
return IndexOf((T)item!);
}
return -1;
}
// Returns the index of the first occurrence of a given value in a range of
// this list. The list is searched forwards, starting at index
// index and ending at count number of elements. The
// elements of the list are compared to the given value using the
// Object.Equals method.
//
// This method uses the Array.IndexOf method to perform the
// search.
//
public int IndexOf(T item, int index)
{
if (index > _size)
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessOrEqualException();
return SegmentedArray.IndexOf(_items, item, index, _size - index);
}
// Returns the index of the first occurrence of a given value in a range of
// this list. The list is searched forwards, starting at index
// index and upto count number of elements. The
// elements of the list are compared to the given value using the
// Object.Equals method.
//
// This method uses the Array.IndexOf method to perform the
// search.
//
public int IndexOf(T item, int index, int count)
{
if (index > _size)
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessOrEqualException();
if (count < 0 || index > _size - count)
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
return SegmentedArray.IndexOf(_items, item, index, count);
}
public int IndexOf(T item, int index, int count, IEqualityComparer<T>? comparer)
{
if (index > _size)
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessOrEqualException();
if (count < 0 || index > _size - count)
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
return SegmentedArray.IndexOf(_items, item, index, count, comparer);
}
// Inserts an element into this list at a given index. The size of the list
// is increased by one. If required, the capacity of the list is doubled
// before inserting the new element.
//
public void Insert(int index, T item)
{
// Note that insertions at the end are legal.
if ((uint)index > (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert);
}
if (_size == _items.Length)
Grow(_size + 1);
if (index < _size)
{
SegmentedArray.Copy(_items, index, _items, index + 1, _size - index);
}
_items[index] = item;
_size++;
_version++;
}
void IList.Insert(int index, object? item)
{
ThrowHelper.IfNullAndNullsAreIllegalThenThrow<T>(item, ExceptionArgument.item);
try
{
Insert(index, (T)item!);
}
catch (InvalidCastException)
{
ThrowHelper.ThrowWrongValueTypeArgumentException(item, typeof(T));
}
}
// Inserts the elements of the given collection at a given index. If
// required, the capacity of the list is increased to twice the previous
// capacity or the new size, whichever is larger. Ranges may be added
// to the end of the list by setting index to the SegmentedList's size.
//
public void InsertRange(int index, IEnumerable<T> collection)
{
if (collection == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
}
if ((uint)index > (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessOrEqualException();
}
if (collection is ICollection<T> c)
{
var count = c.Count;
if (count > 0)
{
if (_items.Length - _size < count)
{
Grow(checked(_size + count));
}
if (index < _size)
{
SegmentedArray.Copy(_items, index, _items, index + count, _size - index);
}
// If we're inserting a SegmentedList into itself, we want to be able to deal with that.
if (this == c)
{
// Copy first part of _items to insert location
SegmentedArray.Copy(_items, 0, _items, index, index);
// Copy last part of _items back to inserted location
SegmentedArray.Copy(_items, index + count, _items, index * 2, _size - index);
}
else if (c is SegmentedList<T> list)
{
SegmentedArray.Copy(list._items, 0, _items, index, list.Count);
}
else if (c is SegmentedArray<T> array)
{
SegmentedArray.Copy(array, 0, _items, index, array.Length);
}
else
{
var targetIndex = index;
foreach (var item in c)
_items[targetIndex++] = item;
}
_size += count;
_version++;
}
}
else
{
using var en = collection.GetEnumerator();
while (en.MoveNext())
{
Insert(index++, en.Current);
}
}
}
// Returns the index of the last occurrence of a given value in a range of
// this list. The list is searched backwards, starting at the end
// and ending at the first element in the list. The elements of the list
// are compared to the given value using the Object.Equals method.
//
// This method uses the Array.LastIndexOf method to perform the
// search.
//
public int LastIndexOf(T item)
{
if (_size == 0)
{ // Special case for empty list
return -1;
}
else
{
return LastIndexOf(item, _size - 1, _size);
}
}
// Returns the index of the last occurrence of a given value in a range of
// this list. The list is searched backwards, starting at index
// index and ending at the first element in the list. The
// elements of the list are compared to the given value using the
// Object.Equals method.
//
// This method uses the Array.LastIndexOf method to perform the
// search.
//
public int LastIndexOf(T item, int index)
{
if (index >= _size)
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();
return LastIndexOf(item, index, index + 1);
}
// Returns the index of the last occurrence of a given value in a range of
// this list. The list is searched backwards, starting at index
// index and upto count elements. The elements of
// the list are compared to the given value using the Object.Equals
// method.
//
// This method uses the Array.LastIndexOf method to perform the
// search.
//
public int LastIndexOf(T item, int index, int count)
{
if (_size == 0)
{
// Special case for empty list
return -1;
}
if (index < 0)
{
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
if (count < 0)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
if (index >= _size)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_BiggerThanCollection);
}
if (count > index + 1)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_BiggerThanCollection);
}
return SegmentedArray.LastIndexOf(_items, item, index, count);
}
public int LastIndexOf(T item, int index, int count, IEqualityComparer<T>? comparer)
{
if (_size == 0)
{
// Special case for empty list
return -1;
}
if (index < 0)
{
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
if (count < 0)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
if (index >= _size)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_BiggerThanCollection);
}
if (count > index + 1)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_BiggerThanCollection);
}
return SegmentedArray.LastIndexOf(_items, item, index, count, comparer);
}
// Removes the first occurrence of the given element, if found.
// The size of the list is decreased by one if successful.
public bool Remove(T item)
{
var index = IndexOf(item);
if (index >= 0)
{
RemoveAt(index);
return true;
}
return false;
}
void IList.Remove(object? item)
{
if (IsCompatibleObject(item))
{
Remove((T)item!);
}
}
// This method removes all items which matches the predicate.
// The complexity is O(n).
public int RemoveAll(Predicate<T> match)
{
if (match == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
var freeIndex = 0; // the first free slot in items array
// Find the first item which needs to be removed.
while (freeIndex < _size && !match(_items[freeIndex]))
freeIndex++;
if (freeIndex >= _size)
return 0;
var current = freeIndex + 1;
while (current < _size)
{
// Find the first item which needs to be kept.
while (current < _size && match(_items[current]))
current++;
if (current < _size)
{
// copy item to the free slot.
_items[freeIndex++] = _items[current++];
}
}
#if NET
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
#endif
{
SegmentedArray.Clear(_items, freeIndex, _size - freeIndex); // Clear the elements so that the gc can reclaim the references.
}
var result = _size - freeIndex;
_size = freeIndex;
_version++;
return result;
}
// Removes the element at the given index. The size of the list is
// decreased by one.
public void RemoveAt(int index)
{
if ((uint)index >= (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRange_IndexMustBeLessException();
}
_size--;
if (index < _size)
{
SegmentedArray.Copy(_items, index + 1, _items, index, _size - index);
}
#if NET
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
#endif
{
_items[_size] = default!;
}
_version++;
}
// Removes a range of elements from this list.
public void RemoveRange(int index, int count)
{
if (index < 0)
{
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
if (count < 0)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
if (_size - index < count)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
if (count > 0)
{
_size -= count;
if (index < _size)
{
SegmentedArray.Copy(_items, index + count, _items, index, _size - index);
}
_version++;
#if NET
if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
#endif
{
SegmentedArray.Clear(_items, _size, count);
}
}
}
// Reverses the elements in this list.
public void Reverse()
=> Reverse(0, Count);
// Reverses the elements in a range of this list. Following a call to this
// method, an element in the range given by index and count
// which was previously located at index i will now be located at
// index index + (index + count - i - 1).
//
public void Reverse(int index, int count)
{
if (index < 0)
{
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
if (count < 0)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
if (_size - index < count)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
if (count > 1)
{
SegmentedArray.Reverse(_items, index, count);
}
_version++;
}
// Sorts the elements in this list. Uses the default comparer and
// Array.Sort.
public void Sort()
=> Sort(0, Count, null);
// Sorts the elements in this list. Uses Array.Sort with the
// provided comparer.
public void Sort(IComparer<T>? comparer)
=> Sort(0, Count, comparer);
// Sorts the elements in a section of this list. The sort compares the
// elements to each other using the given IComparer interface. If
// comparer is null, the elements are compared to each other using
// the IComparable interface, which in that case must be implemented by all
// elements of the list.
//
// This method uses the Array.Sort method to sort the elements.
//
public void Sort(int index, int count, IComparer<T>? comparer)
{
if (index < 0)
{
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
}
if (count < 0)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
if (_size - index < count)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
if (count > 1)
{
SegmentedArray.Sort(_items, index, count, comparer);
}
_version++;
}
public void Sort(Comparison<T> comparison)
{
if (comparison == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.comparison);
}
if (_size > 1)
{
var segment = new SegmentedArraySegment<T>(_items, 0, _size);
SegmentedArraySortHelper<T>.Sort(segment, comparison);
}
_version++;
}
// ToArray returns an array containing the contents of the SegmentedList.
// This requires copying the SegmentedList, which is an O(n) operation.
public T[] ToArray()
{
if (_size == 0)
{
return Array.Empty<T>();
}
var array = new T[_size];
SegmentedArray.Copy(_items, array, _size);
return array;
}
// Sets the capacity of this list to the size of the list. This method can
// be used to minimize a list's memory overhead once it is known that no
// new elements will be added to the list. To completely clear a list and
// release all memory referenced by the list, execute the following
// statements:
//
// list.Clear();
// list.TrimExcess();
//
public void TrimExcess()
{
var threshold = (int)(_items.Length * 0.9);
if (_size < threshold)
{
Capacity = _size;
}
}
public bool TrueForAll(Predicate<T> match)
{
if (match == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
for (var i = 0; i < _size; i++)
{
if (!match(_items[i]))
{
return false;
}
}
return true;
}
public struct Enumerator : IEnumerator<T>, IEnumerator
{
private readonly SegmentedList<T> _list;
private int _index;
private readonly int _version;
private T? _current;
internal Enumerator(SegmentedList<T> list)
{
_list = list;
_index = 0;
_version = list._version;
_current = default;
}
public readonly void Dispose()
{
}
public bool MoveNext()
{
var localList = _list;
if (_version == localList._version && ((uint)_index < (uint)localList._size))
{
_current = localList._items[_index];
_index++;
return true;
}
return MoveNextRare();
}
private bool MoveNextRare()
{
if (_version != _list._version)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
_index = _list._size + 1;
_current = default;
return false;
}
public readonly T Current => _current!;
readonly object? IEnumerator.Current
{
get
{
if (_index == 0 || _index == _list._size + 1)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen();
}
return Current;
}
}
void IEnumerator.Reset()
{
if (_version != _list._version)
{
ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion();
}
_index = 0;
_current = default;
}
}
internal TestAccessor GetTestAccessor()
=> new TestAccessor(this);
internal readonly struct TestAccessor(SegmentedList<T> instance)
{
public ref SegmentedArray<T> Items => ref instance._items;
}
}
}
|